مشبکه (ترتیب)

با مشبکه (گروه) اشتباه نشود.

روابط دوتایی ترایا
متقارن پادمتقارن کانکس خوش-بنیان $\vee$ دارد $\wedge$ دارد بازتابی غیربازتابی نامتقارن رابطه هم‌ارزی ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ پیش‌ترتییب (شبه‌ترتیب) ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ ترتیب جزئی ✗ ✓ ✗ ✗ ✗ ✗ ✓ ✗ ✗ پیش-ترتیب کلی ✗ ✗ ✓ ✗ ✗ ✗ ✓ ✗ ✗ ترتیب کلی ✗ ✓ ✓ ✗ ✗ ✗ ✓ ✗ ✗ پیش-خوش‌ترتیب ✗ ✗ ✓ ✓ ✗ ✗ ✓ ✗ ✗ خوش-شبه-ترتیب ✗ ✗ ✗ ✓ ✗ ✗ ✓ ✗ ✗ خوش‌ترتیب ✗ ✓ ✓ ✓ ✗ ✗ ✓ ✗ ✗ مشبکه ✗ ✓ ✗ ✗ ✓ ✓ ✓ ✗ ✗ جوین-نیم-مشبکه ✗ ✓ ✗ ✗ ✓ ✗ ✓ ✗ ✗ میت-نیم-مشبکه ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✗ ✗ جزئی‌مرتب قطعی ✗ ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✓ مجوعه ضعیف‌مرتب ✗ ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✓ ترتیب کلی قطعی ✗ ✓ ✓ ✗ ✗ ✗ ✗ ✓ ✓ تعاریف: برای تمام $a$ و $b$ ها و $S\neq \varnothing$ : ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
علامت "✓" نشان‌دهنده آن است که ویژگی ستونی در تعریف آن سطر لازم است. برای مثال تعریف رابطه هم‌ارزی لازم دارد تا متقارن باشد. به صورت ضمنی همه این تعاریف ترایا و بازتابی می‌باشند. علامت "✗" نشان‌دهنده آن است که ویژگی به طور کلی تضمین نمی‌شود (می‌تواند برقرار باشد، یا نباشد). تمام روابط بالا مستلزم آن است که رابطه همگون $R$ ترایا باشد: برای تمام $a$ و $b$ و $c$ ها، اگر $aRb$ و $bRc$ آنگاه $aRc$.

یک شبکه دو بعدی

مشبکه (به انگلیسی: Lattice) یا شبکه ساختاری مجرد است که در شاخه های نظریه ترتیب و جبر مجرد در ریاضیات مورد مطالعه قرار می گیرد. مشبکه مجموعه ای با ترتیب جزئی است که در آن هر دو عنصر دارای سوپریمم (همچنین به آن کوچکترین کران بالایی Least Upper Bound یا مخفف آن lub یا جوین Join هم می گویند) و اینفیمم (همچنین به آن بزرگترین کران پایینی Greatest Lower Bound یا مخفف آن glb یا میت Meet هم می گویند) منحصر بفردی اند. یک مثال مشبکه ها اعداد طبیعی اند که توسط رابطه مقسوم علیهی می توان رابطه ترتیب جزئی روی آن تعریف کرد، به طوری که سوپریمم منحصر به فرد آن کوچکترین مضرب مشترک یا ک.م.م. و اینفیمم منحصر به فرد آن بزرگترین مقسوم علیه مشترک یا ب.م.م. است.

مشبکه ها را نیز می توان به صورت ساختارهای جبری دید که برخی از اصول موضوعه در قالب اتحادهایی را ارضاء می کنند. از آنجا که هر دو تعریف مذکور معادل اند، نظریه مشبکه را هم می توان در نظریه ترتیب و هم در جبر جهانی پیگیری کرد. نیم-مشبکه شامل مشبکه‌ها نیز می شود. نیم-مشبکه‌ها نیز به نوبه خود شامل جبر هیتینگ و جبرهای بولی نیز می شوند. تمام این ساختارهای "شبیه مشبکه" را نیز می توان هم از جنبه نظریه ترتیبی و هم جبری توصیف کرد.

مشبکه‌ها به عنوان مجموعه‌های مرتب جزئی

اگر $\left(\geq ,L\right)$ یک مجموعه مرتب جزئی باشد و $S$ یک زیر مجموعه دلخواهی از $L$ باشد، آنگاه $u\in L$ یک کران بالا برای $S$ است اگر به ازای هر $s\in S$ داشته باشیم: $s\leq S$. یک مجموعه ممکن است چند کران بالا داشته باشد یا اصلاً کران بالا نداشته باشد. یک کران بالا $u$ از $S$ را هنگامی کوچکترین کران بالا یا سوپریمم می‌نامیم که به ازای هر کران بالای دیگری چون $x$ داشته باشیم: $u\leq x$ یک مجموعه حتماً کوچکترین کران بالا ندارد ولی نمی‌تواند بیش از یکی داشته باشد. دوگان بحث فوق: $l\in L$ یک کران پایین برای $S$ است اگر به ازای هر $s\in S$ داشته باشیم: $l\leq s$. یک کران پایین $l$ از $S$ را هنگامی بزرگترین کران پایین یا اینفیمم می‌نامیم که به ازای هر کران پایین دیگری چون $x$ داشته باشیم $x\leq 1$. یک مجموعه ممکن است چند کران پایین داشته باشد، یا اصلاً کران پایین نداشته باشد ولی می‌تواند حداکثر یک بزرگترین کران پایین داشته باشد.

یک مجموعه مرتب جزئی $\left(\geq ,L\right)$ را یک جوین-نیم-مشبکه می‌نامند اگر هر زیر مجموعه دو عضوی $\{a,b\}$ از $L$ دارای جوین (یا $a\vee b$) باشد و یک میت-نیم-مشبکه است اگر $\{a,b\}$ مذکور دارای میت (یا $a\wedge b$) باشد. حال $\left(\geq ,L\right)$ یک مشبکه نامیده می‌شود اگر هم یک جوین-نیم-مشبکه و هم یک میت-نیم-مشبکه باشد. این‌ها عمل های دوتایی $\vee$ و $\wedge$ را تعریف می کنند. هر دو عملگر نسبت به ترتیب داده شده خاصیت یکنوایی دارند، یعنی: $a_{1}\leq a_{2}$ و $b_{1}\leq b_{2}$ نتیجه می دهد که $a_{1}\vee b_{1}\leq a_{2}\vee b_{2}$ و $a_{1}\wedge b_{1}\leq a_{2}\wedge b_{2}$.

با استدلال استقرایی ثابت می‌شود که هر زیر مجموعه ناتهی متناهی مشبکه دارای یک سوپریمم و اینفیمم است. با فرض های اضافی، نتیجه‌های بیشتری ممکن است به دست آید. برای ادامه این بحث، مقاله کامل‌بودن را در نظریه ترتیب ببینید. در آن مقاله این که چگونه می توان تعریف بالا را بر اساس وجود الصاق های گالوایی مناسب بین مجموعه های جزئی مرتب مربوط بازنویسی نمود، مورد بحث قرار گرفته است. رهیافت مذکور برای رهیافت نظریه رسته‌ای به مشبکه ها و همچنین برای تحلیل مفهوم صوری مناسب است.

یک مشبکه کراندار، مشبکه‌ای است که دارای بزرگترین عضو (که به آن ماکسیمم یا عنصر بالا هم گفته شده و آن را با $1$ یا $\top$ نیز نشان می دهند) و کوچکترین عضو (که به آن مینیمم یا عنصر پایین هم گفته شده و آن را با $0$ یا $\bot$ نیز نشان می دهند) است به طوری که تمام اعضای آن بین این دو عضو قرار می گیرند:

$\forall x\in L0\leq x\leq 1$

هر مشبکه را می توان در یک مشبکه کراندار با اضافه کردن عناصر جدیدی به عنوان ماکسیمم و مینیمم نشاند، و هر مشبکه متناهی ناتهی کراندار است. چرا که برای یک مشبکه متناهی می توان جوین و میت تمام عناصر را به ترتیب به صورت $\bigvee L=a_{1}\lor \cdots \lor a_{n}$ و $\bigwedge L=a_{1}\land \cdots \land a_{n}$ بدست آورد که در آن ها $L=\{a_{1},\ldots ,a_{n}\}$، سپس این دو را به مشبکه متناهی مورد نظر افزوده و اینگونه به ترتیب ماکسیمم و مینیمم را با مشبکه اجتماع کردیم و اینچنین مشبکه (در صورتی که قبلاً کراندار نبوده است) را کراندار کرده ایم.

یک مجموعه جزئی مشبکه کراندار است اگر و تنها اگر هر زیر مجموعه متناهی از عناصرش دارای جوین و میت باشد. برای هر عنصر $x$ از یک پوست (POSET، مجموعه جزئی مرتب) $\forall a\in \varnothing :x\leq a$ و $\forall a\in \varnothing :a\leq x$ به طور بدیهی برقرار است (یعنی به انتفای مقدم برقرار است) و لذا هر عضو از پوست هم کران بالا و هم پایین مجموعه تهی است. نتیجتاً جوین مجموعه تهی $\bigvee \varnothing =0$ و میت مجموعه تهی $\bigwedge \varnothing =1$ است. این نتیجه گیری با شرکت پذیر بودن و جابجایی بودن میت و جوین سازگار است: جوین اجتماع مجموعه های متناهی برابر جوین جوین های مجموعه هاست، و دوگان آن برای میت هم برقرار است. به طور دقیق تر برای زیرمجموعه های متناهی $A,B\in L$ داریم:

$\bigvee \left(A\cup B\right)=\left(\bigvee A\right)\vee \left(\bigvee B\right)$

و

$\bigwedge \left(A\cup B\right)=\left(\bigwedge A\right)\wedge \left(\bigwedge B\right)$

حال اگر در اتحادهای بالا $B$ تهی باشد اتحادهای زیر بدست می آیند:

$\bigvee \left(A\cup \emptyset \right)=\left(\bigvee A\right)\vee \left(\bigvee \emptyset \right)=\left(\bigvee A\right)\vee 0=\bigvee A$

و

$\bigwedge \left(A\cup \emptyset \right)=\left(\bigwedge A\right)\wedge \left(\bigwedge \emptyset \right)=\left(\bigwedge A\right)\wedge 1=\bigwedge A$

که با این حقیقت که $A\cup \emptyset =A$ سازگار است.

گویند که یک عنصر دلخواهی از مشبکه چون $y$، عنصر دیگری چون $x$ را پوشش می دهد اگر $y>x$، اما هیچ عنصری چون $z$ وجود نداشته باشد به طوری که $y>z>x$. در اینجا $y>x$ به معنای $x\leq y$ و $x\neq y$ است.

گویند مشبکه $\left(L,\leq \right)$ مدرج است (برخی مواقع به آن رتبه‌ای نیز می گویند، اما با پوست رتبه ای یا Ranked POSET اشتباه نشود) اگر بتوان آن را مجهز به تابع رتبه کرد. این تابع با r نامگذاری شده و از $L$ به $\mathbb {N}$ می رود، برخی مواقع هم-دامنه آن $\mathbb {Z}$ است. ویژگی این تابع سازگاری با ترتیب است (یعنی از $x<y$ نتیجه می شود $r(x)<r(y)$)، چنان که هرگاه $y$ عنصر $x$ را بپوشاند خواهیم داشت $r(y)=r(x)+1$. مقدار تابع رتبه برای یک عنصر مشبکه را رتبه آن عنصر گویند.

برای زیرمجموعه دلخواهی از یک مشبکه چون $H\subseteq L$، میت و جوین محدود به توابع جزئی (یعنی دیگر بر روی کل دامنه تعریف نمی شوند) می شوند، اینگونه که اگر مقادیر میت و جوین یک عنصر در زیرمجموعه $H$ نباشد، میت و جوین آن عنصر تعریف نشده در نظر گرفته می شود. ساختار حاصل روی $H$ را مشبکه جزئی گویند. به علاوه این تعریف برونگرا که مشبکه را بر اساس ساختار جبری دیگری (یعنی مشبکه دیگری) تعریف می کند، یک مشبکه جزئی را به صورت ذاتی و درونگرا نیز می توان تعریف کرد، اینگونه که میت و جوین را به صورت توابع جزئی تعریف کنیم که در اصول موضوعه های خاصی صدق کنند.

مشبکه‌ها به عنوان ساختارهای جبری

مشبکه عمومی

مشبکه یک ساختار جبری ${\displaystyle }$ شامل مجموعه ای چون ${\displaystyle }$ مجهز به دو عمل دوتایی جابجایی شرکت پذیر ${\displaystyle }$ و ${\displaystyle }$ روی ${\displaystyle }$ است، به طوری که برای هر ${\displaystyle }$ اتحادهی زیر به نام قوانین جذب برقرار باشند:

$a\vee (a\wedge b)=a$

$a\wedge (a\vee b)=a$

دو اتحاد زیر که از قوانین جذب نتیجه می شوند نیز در برخی منابع به عنوان اصول موضوعه چنین مشبکه هایی قید می شوند. به این اتحادها قوانین خودتوانی می گویند:

$a\vee a=a$

$a\wedge a=a$

این اصول موضوعه ها بیان می دارند که $(L,\vee )$ و $(L,\wedge )$ هردو نیم-مشبکه اند. قوانین جذب، تنها قوانینی از دو قانون فوق اند که در هردو هم از جوین استفاده شده و هم از میت و این باعث می شود که بین مشبکه و یک جفت ساختار دلخواه نیم-مشبکه تمایز ایجاد شده و بین دو نیم-مشبکه روابط مناسبی برقرار شود. به‌خصوص، هر نیم-مشبکه دوگان دیگری است.

اشکال مشبکه

یک مفهوم مناسب از ریخت (شکل) بین دو مشبکه به آسانی از تعریف جبری بالا بر می‌آید. دو مشبکه (L, ∨L, ∧L) و (M, ∨M, ∧M) در نظر بگیرید. یک مشبکه هم ریخت از Lبه M به صورت تابع f: L است که M شامل همهٔ a,bهایی عضو L است. f(a∨Lb) = f(a) ∨M f(b), and f(a∧Lb) = f(a) ∧M f(b). بنابراین f یک هم‌ریخت از دو شبه مشبکه است. هم چنین وقتی که مشبکه‌هایی با ساختارهای بیشتری در نظر گرفته شوند، ریخت‌ها بایستی به بیشترین ساختار نسبت داشته باشند. به ویژه در یک مشبکه هم ریخت محدود (که معمولاً همان «مشبکه همریخت» گفته می‌شود) تابع f بین دو مشبکه کران دار L و M ویژگی زیر را داراست: f(0L) = 0M f(1L) = 1M

طبق ترتیب فرمول بندی نظری این شرایط تنها بیان می‌کند که مشبکه‌ها تابعیست که تلاقی و اتصال‌های دودویی را حفظ می‌کند. برای مشبکه‌های کران دار حفظ کردن کوچکترین و بزرگترین عنصر در واقع همان حفظ تلاقی و اتصال یک مجموعه خالی است. هر هم ریختی مشبکه‌ها الزاماٌ یک رابطه ترتیبی یکنوا است. اما برعکس این مطلب درست نیست. اگرچه ترتیب دو طرفه حفظ شونده یک هم ریخت است اگر وارون ان هم یک ترتیب حفظ شونده باشد.

یک مشبکه یک ریخت در واقع یک مشبکه هم ریخت دو طرفه است. متشابها یک مشبکه درون ریخت یک مشبکه هم ریخت است از یک مشبکه درون خودش. هم چنین یک مشبکه خود ریخت یک مشبکه دو طرفه درون ریخت است. در واقع مشبکه‌ها و هم ریخت‌های آن‌ها یک دسته را تشکیل می‌دهند.

زیرمشبکه‌ها

یک زیرمشبکه از مشبکه L یک مجموعه غیر تهی است ازL که در واقع مشبکه ایست با تلاقی و اتصال‌هایی مشابه L یک زیرمشبکه M از یک مشبکه L یک زیر مشبکه برجسته L است اگرx ≤ z ≤ y و x,yموجود در M نشان می‌دهد که zمتعلق به M است برای هر x,y،zعضوL.

ویژگی مشبکه‌ها

در زیر تعدادی از ویژگی‌های مهم یک مشبکه مطرح شده است:

تمامیت (کمال)

یک مجموعه مرتب جزئی مشبکه کامل نامیده می‌شود اگر همهٔ زیر مجموعه‌هایش هر دوی اتصال و تلاقی را دارا باشند. به ویژه هر مشبکه کامل یک مشبکه کران دار است. در حالیکه مشبکه‌های کران دار هم ریخت در کل فقط اتصال و تلاقی ::متناهی را حفظ می‌کنند مشبکه‌های کامل هم ریخت می‌بایستی ::اتصال و ::تلاقی دلخواه را حفظ کنند. هر مجموعه مرتب جزئی که یک زیر مشبکه کامل است یک مشبکه کامل نیز می‌باشد. شایان ذکر است که مشبکه جزئی در تضاد با مشبکه کامل نیست زیرا کلیهٔ مفهوم‌های مشبکه و مشبکه کامل و مشبکه جزئی تعاریفی محدود هستند.

تکامل شرطی

یک مشبکه کامل مشروط مشبکه ایست که هر زیرمجموعه ناتهی که کران بالا دارد یک نقطه اتصال دارد (منظور از کران بالا کوچکترین کران بالا است)

توزیع‌پذیری

هنگامیکه مشبکه‌ها در عملیات دودویی قرار گیرند این رایج است که سؤال شود کدام یک بر دیگری توزیع پذیر است. توزیع‌پذیری عطف و فصل: a∨(b∧c) = (a∨b) ∧ (a∨c). a∧(b∨c) = (a∧b) ∨ (a∧c).

پیمانه‌ای

برای بسیاری از عملیات خاصیت توزیع‌پذیری سنگین بوده و خاصیت پیمانه‌ای به جای ان قرار می‌گیرد. ماهیت پیمانه‌ای بودن: (a ∧ c) ∨ (b ∧ c) = [(a ∧ c) ∨ b] ∧ c

قانون پیمانه‌ای

اگر a<=c: a ∨ (b ∧ c) = (a ∨ b) ∧ c

مشبکه‌های ازاد

هر مجموعهٔ X برای تولید زیر مشبکه‌های آزاد FX مورد استفاده قرار می‌گیرد. یک زیر مشبکه آزاد شامل تمامی زیر مجموعه‌های متناهی X است.

پانویس

• مشارکت‌کنندگان ویکی‌پدیا. «Lattice (order)». در دانشنامهٔ ویکی‌پدیای انگلیسی.

منابع

تک نویس های آزاد آنلاین:

• Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. شابک ‎۳−۵۴۰−۹۰۵۷۸−۲.
• Jipsen, Peter, and Henry Rose, Varieties of Lattices, Lecture Notes in Mathematics 1533, Springer Verlag, 1992. شابک ‎۰−۳۸۷−۵۶۳۱۴−۸.
• Nation, J. B., Notes on Lattice Theory. Chapters 1-6. Chapters 7–12; Appendices 1–3.

متون مقدماتی برای کسانی که به بلوغ ریاضیاتی نرسیده اند:

• Donnellan, Thomas, 1968. Lattice Theory. Pergamon.
• Grätzer, G., 1971. Lattice Theory: First concepts and distributive lattices. W. H. Freeman.

متون استاندارد معاصر که کمی از منابع بالا سخت ترند:

• Davey, B.A.; Priestley, H. A. (2002), Introduction to Lattices and Order, Cambridge University Press, ISBN 978-0-521-78451-1

تک نویس های پیشرفته:

• Garrett Birkhoff, 1967. Lattice Theory, 3rd ed. Vol. 25 of AMS Colloquium Publications. American Mathematical Society.
• Robert P. Dilworth and Crawley, Peter, 1973. Algebraic Theory of Lattices. Prentice-Hall. شابک ‎۹۷۸−۰−۱۳−۰۲۲۲۶۹−۵.
• Grätzer, George (1996) [1978]. General Lattice Theory (Second ed.). Basel: Birkhäuser. ISBN 978-3-7643-6996-5.

در ارتباط با مشبکه های آزاد:

• R. Freese, J. Jezek, and J. B. Nation, 1985. "Free Lattices". Mathematical Surveys and Monographs Vol. 42. Mathematical Association of America.
• Johnstone, P.T., 1982. Stone spaces. Cambridge Studies in Advanced Mathematics 3. Cambridge University Press.

در ارتباط با تاریخچه نظریه مشبکه ها:

• Štĕpánka Bilová (2001). Eduard Fuchs (ed.). Lattice theory — its birth and life (PDF). Prometheus. pp. 250–257. Archived from the original (PDF) on 17 May 2017. Retrieved 15 September 2019.

در مورد کاربرد های نظریه مشبکه ها:

• Garrett Birkhoff (1967). James C. Abbot (ed.). What can Lattices do for you?. Van Nostrand. Table of contents